package com.bjsxt.jy;

import java.util.Arrays;

/**
 * @auther:YU JIANG
 * @date:2021/7/1
 * @time:13:05
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr={888,777,666,555,444,333,222,111,1};
        int[] temp = new int[arr.length];
        divide3(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

    public static void divide(int[] arr,int left,int right,int[] temp){
        if (left<right){
            int mid = (left+right)/2;
            //向左分
            divide(arr,left,mid,temp);
            //向右分
            divide(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }

    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;
        int j = mid+1;
        int t = 0;

        while (i<=mid && j<=right){

            if (arr[i]<=arr[j]){
                temp[t++] = arr[i];
                i++;
            }else {
                temp[t++] = arr[j];
                j++;
            }

        }

        while (i<=mid){
            temp[t++]=arr[i++];
        }
        while (j<=right){
            temp[t++]=arr[j++];
        }

        int tempLeft=left;
        t=0;
        while (tempLeft<=right){
            arr[tempLeft++]=temp[t++];
        }
    }

    public static void merge2(int[] arr,int left,int mid,int right,int[] temp){
        //左组起始下标
        int i = left;
        //右组起始下标
        int j = mid+1;
        //临时数组下标
        int t = 0;

        while (i<=mid && j<=right){
            //左右互相比较，小的放入临时数组
            if (arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }

        //处理剩余部分
        while (i<=mid){
            temp[t++] = arr[i++];
        }
        while (j<=right){
            temp[t++] = arr[j++];
        }

        //拷贝数据
        int tempLeft=left;
        t=0;
        while (tempLeft<=right){
            arr[tempLeft++] = temp[t++];
        }
    }

    public static void divide2(int[] arr,int left,int right,int[] temp){
        if (left<right){
            int mid = (left+right)/2;
            //向左分
            divide2(arr,left,mid,temp);
            //向右分
            divide2(arr,mid+1,right,temp);
            //合并
            merge2(arr,left,mid,right,temp);

        }
    }

    public static void merge3(int[] arr,int left,int mid,int right,int[] temp){
        /*左组起始下标*/
        int i=left;
        /*右组起始下标*/
        int j=mid+1;
        //临时数组起始下标
        int t = 0;

        //两组互相比较找到最小值然后放入临时数组
        while (i<=mid && j<=right){

            if (arr[i]<=arr[j]){
                temp[t++]=arr[i++];
            }else {
                temp[t++]=arr[j++];
            }
        }

        //处理剩余的数
        while (i<=mid){
            temp[t++]=arr[i++];
        }

        while (j<=right){
            temp[t++]=arr[j++];
        }

        //把临时数组拷贝到原数组
        t=0;
        int tempLeft=left;
        while (tempLeft<= right){
            arr[tempLeft++] = temp[t++];
        }
    }

    public static void divide3(int[] arr,int left,int right,int[] temp){
        if (left<right){
            int mid = (left+right)/2;
            //向左分
            divide3(arr,left,mid,temp);
            //向右分
            divide3(arr,mid+1,right,temp);
            //合并
            merge3(arr,left,mid,right,temp);
        }
    }
}
